package com.zx._12_算法.数据结构.link;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Linked 实现双向链表（地狱模式）
 *         append， 添加一个新的元素
 *         insert，在指定位置插入一个元素
 *         remove，删除指定位置的节点
 *         remove_head，删除首节点
 *         remove_tail，删除尾节点
 *         indexOf，返回指定元素的索引
 *         get，返回指定索引位置的元素
 *         head，返回首节点
 *         tail，返回尾节点
 *         length，返回链表长度
 *         isEmpty，判断链表是否为空
 *         clear，清空链表
 *         print，打印整个链表
 * @author: zhangxue
 * @date: 2019年7月27日上午9:55:18
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Link2<T> {

    // 头节点
    private Node<T> head;

    // 尾节点
    private Node<T> tail;

    private int size;

    public static void main(String[] args) {
        Link2<String> link = new Link2<>();
        link.print();//link = []
        link.printTail();//link = []

        link.append("1");
        link.append("2");
        link.append("3");
        link.append("4");
        link.append("5");
        link.append("6");
        link.print();        //link = [1, 2, 3, 4, 5, 6]
        link.printTail();    //link = [6, 5, 4, 3, 2, 1]

        link.insert(0, "0");// 开头插入数据
        link.insert(7, "7");//末尾插入数据
        link.insert(5, "4.5");// 中间任意位置插入数据
        link.print();        //link = [0, 1, 2, 3, 4, 4.5, 5, 6, 7]
        link.printTail();    //link = [7, 6, 5, 4.5, 4, 3, 2, 1, 0]

        link.remove(0);
        link.remove(8);
        link.print();        //link = [1, 2, 3, 4, 4.5, 5, 6]
        link.printTail();    //link = [6, 5, 4.5, 4, 3, 2, 1]

        link.removeHead();
        link.removeTail();
        link.print();        //link = [2, 3, 4, 4.5, 5]
        link.printTail();    //link = [5, 4.5, 4, 3, 2]

        link.remove(3);
        link.print();        //link = [2, 3, 4, 5]
        link.printTail();    //link = [5, 4, 3, 2]

        System.out.println(link.indexOf("5"));// 3
        System.out.println(link.get(1));//3
        System.out.println(link.head());//2
        System.out.println(link.tail());//5
        System.out.println(link.length());//4
        System.out.println(link.isEmpty());//false
        link.clear();

        link.print();//link = []
        link.printTail();//link = []
    }

    public void append(T data) {
        Node<T> node = this.createNode(data);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            node.pre = tail;
            tail = node;
        }
        size++;
    }

    public void insert(int index, T data) {
        Node<T> newNode = this.createNode(data);

        // 在开头插入
        if (index == 0) {
            newNode.next = head;
            head.pre = newNode;
            head = newNode;
            size++;
            return;
        }
        // 在最后插入
        if (index == size) {
            append(data);
            return;
        }
        // 中间位置插入
        Node<T> indexNode = getNode(index);
        Node<T> indexBeforeNode = indexNode.pre;
        if (indexBeforeNode == null || indexNode == null) {
            return;
        }

        indexBeforeNode.next = newNode;

        newNode.pre = indexBeforeNode;
        newNode.next = indexNode;

        indexNode.pre = newNode;
        size++;
    }

    public void remove(int index) {
        // 在开头
        if (index == 0) {
            this.removeHead();
            return;
        }
        // 在最后
        if (index == size) {
            this.removeTail();
            return;
        }
        // 中间位置
        Node<T> removeNode = getNode(index);// 需要删除的节点
        Node<T> removePreNode = removeNode.pre;
        Node<T> removeNextNode = removeNode.next;
        if (removeNode == null || removePreNode == null || removeNextNode == null) {
            return;
        }

        removePreNode.next = removeNextNode;
        removeNextNode.pre = removePreNode;
        size--;
    }

    public void removeHead() {
        head.pre = null;
        head = head.next;
        size--;
    }

    public void removeTail() {
        if (tail == null || tail.pre == null) {//没有上一个节点
            tail = null;
            head = null;
            size = 0;
        } else {
            tail = tail.pre;
            tail.next = null;
            size--;
        }
    }

    public int indexOf(T data) {
        Node<T> node = this.head;
        int index = 0;
        while (node != null) {
            if (node.data.equals(data)) {
                return index;
            }
            node = node.next;
            index++;
        }
        return -1;
    }

    public T get(int index) {
        Node<T> node = this.getNode(index);
        return node == null ? null : node.data;
    }

    public T head() {
        return this.head.data;
    }

    public T tail() {
        return this.tail.data;
    }

    public int length() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void clear() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void print() {
        String s = "";
        Node<T> node = this.head;

        for (int i = 0; i < size; i++) {
            s += (i == size - 1) ? node.data : node.data + ", ";
            node = node.next;
        }

        System.out.println("link = [" + s + "]");
    }

    public void printTail() {
        String s = "";
        Node<T> node = this.tail;

        for (int i = 0; i < size; i++) {
            s += (i == size - 1) ? node.data : node.data + ", ";
            node = node.pre;
        }

        System.out.println("link = [" + s + "]");
    }

    private Node<T> getNode(int index) {
        if (size - 1 < index) {
            return null;
        }
        Node<T> node = head;
        for (int i = 1; i <= index; i++) {
            node = node.next;
        }
        return node;
    }

    private Node<T> createNode(T data) {
        Node<T> node = new Node<>();
        node.data = data;
        return node;
    }

    @SuppressWarnings("hiding")
    class Node<T> {

        T data;
        Node<T> next;
        Node<T> pre;
    }
}
